package chapter1.bagqueuestack.example;

import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdIn;
import test.FixedCapacityStackOfStrings;


/**
 * Dijkstra的双栈算术表达式求值算法
 *
 * @author quanlinlin on 2018/11/27 9:49.
 * @version 1.0
 */
public class Evaluate {

    public static void main(String[] args) {
        //运算符栈
        Stack<String> ops = new Stack<>();
        //操作数栈
        Stack<Double> vals = new Stack<>();
        while (!StdIn.isEmpty()) {
            //读取字符，如果是运算符则压入栈
            String s = StdIn.readString();
            if ("(".equals(s)) {
            } else if ("+".equals(s)) {
                ops.push(s);

            } else if ("-".equals(s)) {
                ops.push(s);

            } else if ("*".equals(s)) {
                ops.push(s);

            } else if ("/".equals(s)) {
                ops.push(s);

            } else if ("sqrt".equals(s)) {
                ops.push(s);

            } else if (")".equals(s)) {//如果字符为“）”，弹出运算符和操作数，计算结果并压入栈
                String op = ops.pop();
                Double v = vals.pop();
                if ("+".equals(op)) {
                    v = vals.pop() + v;

                } else if ("-".equals(op)) {
                    v = vals.pop() - v;

                } else if ("*".equals(op)) {
                    v = vals.pop() * v;

                } else if ("/".equals(op)) {
                    v = vals.pop() / v;

                } else if ("sqrt".equals(op)) {
                    v = Math.sqrt(v);

                }
                vals.push(v);

            } else {
                vals.push(Double.parseDouble(s));

            }
        }
        System.out.println(vals.pop());

        new FixedCapacityStackOfStrings(3);
    }


}
